package com.arron.algorithm.leetcodetop100.回溯.排列and组合and子集;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 组合总和 {


    List<List<Integer>> allSubList;
    int sum;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        allSubList = new ArrayList<>();
        List<Integer> subList = new ArrayList<>();

        subsets(candidates,subList,0,target);
        return allSubList;
    }

    public void subsets(int[] candidates,List<Integer> subList,int start,int target){

        if (sum == target){
            allSubList.add(new ArrayList<>(subList));
            return;
        }

        if (sum > target){
            return;
        }

        for (int i = start; i < candidates.length; i++) {

            subList.add(candidates[i]);
            sum = sum + candidates[i];
            subsets(candidates,subList,i,target);
            sum = sum - candidates[i];
            subList.remove(subList.size()-1);
        }

    }


}
